package main.Q1_100;

import java.util.*;

public class Q31_40 {
    public static void main(String[] args) {
        System.out.println("Question31：下一个排列");
        System.out.println("Question32：最长有效括号");
        System.out.println("Question33：搜索旋转排序数组");
        System.out.println("Question34：在排序数组中查找元素的第一个和最后一个位置");
        System.out.println("Question35：搜索插入位置");
        System.out.println("Question36：有效的数独");
        System.out.println("Question37：解数独");
        System.out.println("Question38：外观数列");
        System.out.println("Question39：组合总和");
        System.out.println("Question40：组合总和Ⅱ");
    }
}

class Question31 {
    public void process1(int[] nums, int i, int j) {//交换
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    public void process2(int[] nums, int start) {//逆置
        int left = start, right = nums.length - 1;
        while (left < right) {
            process1(nums, left, right);
            left++;
            right--;
        }
    }

    public void nextPermutation(int[] nums) {
        int i = nums.length - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) i--;//寻找首个升序对
        if (i >= 0) {
            int j = nums.length - 1;
            while (j >= 0 && nums[i] >= nums[j]) j--;//寻找首个大数
            process1(nums, i, j);//交换
        }
        process2(nums, i + 1);//逆置
    }
}

class Question32 {
    public int longestValidParentheses(String s) {
        int maxLength = 0, length = s.length();
        int[] dp = new int[length];
        char[] str = s.toCharArray();
        for (int i = 1; i < length; i++) {
            if (str[i] == ')') {//右括号才存在
                if (str[i - 1] == '(' && i - 2 >= 0) dp[i] = dp[i - 2] + 2;//相邻左侧为(且之前还存在有效括号
                else if (str[i - 1] == '(' && i - 2 < 0) dp[i] = 2;//相邻左侧为(且之前不存在有效括号
                else if (i - dp[i - 1] > 0 && str[i - dp[i - 1] - 1] == '(' && i - dp[i - 1] - 2 >= 0)
                    dp[i] = dp[i - 1] + dp[i - dp[i - 1] - 2] + 2;//存在嵌套括号且满足有效
                else if (i - dp[i - 1] > 0 && str[i - dp[i - 1] - 1] == '(' && i - dp[i - 1] - 2 < 0)
                    dp[i] = dp[i - 1] + 2;//存在嵌套括号且不满足有效
                maxLength = Math.max(maxLength, dp[i]);
            }
        }
        return maxLength;
    }
}

class Question33 {
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1, result = -1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] == target) {
                result = mid;
                break;
            } else {
                if (nums[left] <= nums[mid]) {//左侧有序
                    if (target >= nums[left] && target <= nums[mid]) right = mid - 1;//target在有序范围内
                    else left = mid + 1;//target不在有序范围内
                } else {//右侧有序
                    if (target >= nums[mid] && target <= nums[right]) left = mid + 1;//target在有序范围内
                    else right = mid - 1;
                }
            }
        }
        return result;
    }
}

class Question34 {
    public int[] searchRange(int[] nums, int target) {
        int[] result = new int[]{-1, -1};
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = (right + left) / 2;
            if (target == nums[mid]) {// 存在target
                int start = mid, end = mid;
                while (start >= 0) {// 左扩
                    if (start - 1 >= 0 && nums[start - 1] == target) {
                        start--;
                    } else {
                        break;
                    }
                }
                while (end < nums.length) {// 右扩
                    if (end + 1 < nums.length && nums[end + 1] == target) {
                        end++;
                    } else {
                        break;
                    }
                }
                result[0] = start;
                result[1] = end;
                break;
            } else if (target > nums[mid]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return result;
    }
//    public int[] searchRange(int[] nums, int target) {
//        int leftIdx = binarySearch(nums, target, true);
//        int rightIdx = binarySearch(nums, target, false) - 1;
//        if (leftIdx <= rightIdx && rightIdx < nums.length && nums[leftIdx] == target && nums[rightIdx] == target) {
//            return new int[]{leftIdx, rightIdx};
//        }
//        return new int[]{-1, -1};
//    }
//
//    public static int binarySearch(int[] nums, int target, boolean lower) {
//        int left = 0, right = nums.length - 1, ans = nums.length;
//        while (left <= right) {
//            int mid = (left + right) / 2;
//            if (nums[mid] > target || (lower && nums[mid] >= target)) {
//                right = mid - 1;
//                ans = mid;
//            } else {
//                left = mid + 1;
//            }
//        }
//        return ans;
//    }
}

class Question35 {
    public int searchInsert(int[] nums, int target) {
        int index = -1;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == target || nums[i] > target) {
                index = i;
                break;
            }
        }
        if (index == -1) index = nums.length;
        return index;
    }
}

class Question36 {
    public boolean isValidSudoku(char[][] board) {
        int[][] rows = new int[9][9];
        int[][] columns = new int[9][9];
        int[][][] subboxes = new int[3][3][9];
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                char c = board[i][j];
                if (c != '.') {
                    int index = c - '0' - 1;
                    rows[i][index]++;
                    columns[j][index]++;
                    subboxes[i / 3][j / 3][index]++;
                    if (rows[i][index] > 1 || columns[j][index] > 1 || subboxes[i / 3][j / 3][index] > 1) {
                        return false;
                    }
                }
            }
        }
        return true;
    }
}

class Question37 {
    private boolean[][] line = new boolean[9][9];
    private boolean[][] column = new boolean[9][9];
    private boolean[][][] block = new boolean[3][3][9];
    private boolean valid = false;
    private List<int[]> spaces = new ArrayList<int[]>();

    public void process(char[][] board, int pos) {
        if (pos == spaces.size()) {
            valid = true;
            return;
        }

        int[] space = spaces.get(pos);
        int i = space[0], j = space[1];
        for (int digit = 0; digit < 9 && !valid; ++digit) {
            if (!line[i][digit] && !column[j][digit] && !block[i / 3][j / 3][digit]) {
                line[i][digit] = column[j][digit] = block[i / 3][j / 3][digit] = true;
                board[i][j] = (char) (digit + '0' + 1);
                process(board, pos + 1);
                line[i][digit] = column[j][digit] = block[i / 3][j / 3][digit] = false;
            }
        }
    }

    public void solveSudoku(char[][] board) {
        for (int i = 0; i < 9; ++i) {
            for (int j = 0; j < 9; ++j) {
                if (board[i][j] == '.') {
                    spaces.add(new int[]{i, j});
                } else {
                    int digit = board[i][j] - '0' - 1;
                    line[i][digit] = column[j][digit] = block[i / 3][j / 3][digit] = true;
                }
            }
        }
        process(board, 0);
    }
}

class Question38 {
    public String process(String last) {
        StringBuffer describe = new StringBuffer();
        char[] str = last.toCharArray();
        int i = 0, length = str.length, count = 0;
        char temp = str[0];
        while (i < length) {
            if (temp == str[i]) count++;//计数
            else if (temp != str[i]) {//描述
                describe.append(count);
                describe.append(temp);
                temp = str[i];
                count = 1;
            }
            i++;
        }
        describe.append(count);
        describe.append(temp);
        return describe.toString();
    }

    public String countAndSay(int n) {
        String start = "1";
        for (int i = 1; i < n; i++) {
            start = process(start);
        }
        return start;
    }
}

class Question39 {
    List<List<Integer>> list = new ArrayList<>();

    public void process(int[] candidates, int cur, List<Integer> curList, int start) {
        if (cur == 0) {
            list.add(curList);
            return;
        }
        if (cur < 0) return;
        for (int i = start; i < candidates.length; i++) {
            List<Integer> tempList = new ArrayList<>(curList);
            tempList.add(candidates[i]);
            process(candidates, cur - candidates[i], tempList, i);
        }
    }

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<Integer> curList = new ArrayList<>();
        process(candidates, target, curList, 0);
        return list;
    }
}

class Question40 {
    List<List<Integer>> lists = new ArrayList<>();
    Deque<Integer> deque = new LinkedList<>();
    int sum = 0;

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        //为了将重复的数字都放到一起，所以先进行排序
        Arrays.sort(candidates);
        //加标志数组，用来辅助判断同层节点是否已经遍历
        boolean[] flag = new boolean[candidates.length];
        backTracking(candidates, target, 0, flag);
        return lists;
    }

    public void backTracking(int[] arr, int target, int index, boolean[] flag) {
        if (sum == target) {
            lists.add(new ArrayList(deque));
            return;
        }
        for (int i = index; i < arr.length && arr[i] + sum <= target; i++) {
            //出现重复节点，同层的第一个节点已经被访问过，所以直接跳过
            if (i > 0 && arr[i] == arr[i - 1] && !flag[i - 1]) {
                continue;
            }
            flag[i] = true;
            sum += arr[i];
            deque.push(arr[i]);
            //每个节点仅能选择一次，所以从下一位开始
            backTracking(arr, target, i + 1, flag);
            int temp = deque.pop();
            flag[i] = false;
            sum -= temp;
        }
    }
}